package class05_06_mergeSortRelated;

public class ReversePairsPlus {
    public static int mergeAndReversePair(int[] arr, int l, int m, int r){
        int[] temp = new int[r-l+1];
        int reversePairCounter = 0;
        int pointer1 = l;
        int pointer2 = m+1;
        int pointerMerge = 0;

        //不回退的向前遍历 O(n)
        while(pointer1<m+1){
            while(pointer2<r+1 && arr[pointer1] > arr[pointer2]*2)pointer2++;
            reversePairCounter += (pointer2-m-1);
            pointer1++;
        }

        pointer1 = l;
        pointer2 = m+1;


        while(pointerMerge<temp.length){
            if(pointer1>m){
                temp[pointerMerge] = arr[pointer2++];
            } else if (pointer2>r) {
                temp[pointerMerge] = arr[pointer1++];
            } else if(arr[pointer1] <= arr[pointer2]) {
                temp[pointerMerge] = arr[pointer1++];
            } else {
                temp[pointerMerge] = arr[pointer2];
                //if(arr[pointer1] > arr[pointer2]*2) reversePairCounter += (pointer2-m);
                pointer2++;
            }
            pointerMerge++;
        }

        for (int i = 0; i<temp.length; i++){
            arr[l+i] = temp[i];
        }

        return reversePairCounter;
    }

    public static int mergeSortAndReversePair(int[] arr){
        int groupSize = 1;
        int reversePair = 0;

        while(groupSize<arr.length){
            int l = 0;
            int r = l+groupSize*2-1;
            int m = (l+r)/2;

            while(m<arr.length-1){
                if(r>=arr.length) reversePair += mergeAndReversePair(arr,l,m, arr.length-1);
                else reversePair += mergeAndReversePair(arr,l,m, r);
                l = r+1;
                r = l+groupSize*2-1;
                m = (l+r)/2;
            }

            groupSize*=2;
        }
        return reversePair;
    }

    public static int getReversePairN2(int[] arr){
        int reversePairCounter = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j=0; j<i; j++){
                if(arr[j]>arr[i]*2) reversePairCounter++;
            }
        }
        return reversePairCounter;
    }

    //for test
    public static int[] randomArr (int maxLen,int maxValue)
    {
        int len = (int)(maxLen*Math.random());
        int[] arr =new int[len];

        for(int i = 0; i<len; i++)
        {
            arr[i] = (int)(maxValue*Math.random());
        }
        return arr;
    }

    //for test
    public static boolean isOrder(int[] arr)
    {
        int len = arr.length;

        for(int i = 0; i<len-1; i++)
        {
            if(arr[i+1]<arr[i])
            {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int[] arr = randomArr(100,100);
        //int[] arr = {3,3,4,1};
        //for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
        System.out.println(getReversePairN2(arr));

        System.out.println(mergeSortAndReversePair(arr));
        //for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
        System.out.println(isOrder(arr));
    }
}
